package linkedList;

import linkedList.entity.ListNode;

/**
 * @program: leetcode
 * @description: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 示例 1：
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 * @author: lxf
 * @create: 2024-03-14 22:36
 **/
public class MergeTwoLists {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode head1 = list1;
        ListNode p = new ListNode(2);
        head1.next = p;
        head1 = p;
        ListNode p1 = new ListNode(4);
        head1.next = p1;

        ListNode list2 = new ListNode(1);
        ListNode head2 = list2;
        ListNode p2 = new ListNode(3);
        head2.next = p2;
        head2 = p2;
        ListNode p3 = new ListNode(4);
        head2.next = p3;

        ListNode list3 = null;
        ListNode list4 = new ListNode(1);

        ListNode node1 = mergeTwoLists3(list1, list2);
        System.out.println(1);

    }

    //固定list1，然后插入list2
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //设置假头，因为list1可能为null
        ListNode head = new ListNode(-1);
        head.next = list1;
        ListNode l1 = list1;
        ListNode l2 = list2;
        //设置前置节点，即l2节点往l1插入的前置节点，在l1前。
        ListNode pre = head;
        //只要有一个链表没走完，循环继续
        while (l1 != null || l2 != null) {
            //如果l1链表走到尾，pre指向最后一个元素，无论l2是否为null都接上l2
            if (l1 == null) {
                pre.next = l2;
                break;
            //如果l2链表走到尾，就结束循环，即l2的元素都已经插入完毕
            } else if (l2 == null){
                break;
            //如果l2节点的值小于l1节点的值，就把l2插入到l1前面，即pre的后面
            //l2后挪，pre后挪
            }else if (l1.val >= l2.val) {
                ListNode next = l2.next;
                pre.next = l2;
                l2.next = l1;
                l2 = next;
            //如果l2节点的值大于l1节点的值，l1后挪，pre伴随后挪
            } else {
                l1 = l1.next;
            }
            pre = pre.next;
        }
        return head.next;
    }

    //递归实现合并两个链表，固定list不动，插入list2
    /*
            1 -> 2 -> 4 , 1 -> 3 -> 4
  层        栈的顺序：
  0         list1           list2         传参
  1         1->2->4         1->3->4
  2         1->1->2->4      3->4          (1->2->4,3->4)    l2插入，l1变化          ....
  3         1->2->4         3->4          (2->4,3->4)       不符合，l1继续指向       ....
  4         2->4            3->4          (4,3->4)          不符合，l1继续指向       list1此时是2，next指向3->4->4，返回2->3->4->4
  5         3->4            4             (4,4)             不符合，l1继续指向       list1此时是3，next指向4->4，返回3->4->4
  6         4->4            null          (4,null)          l2插入，l1变化          list1此时是4，next指向4，返回4->4
  7         4               返回给上一层                       开始返回list1          返回4
            *
            * */
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list2 == null){
            return list1;
        }
        if (list1 == null){
            return list2;
        }
        if (list1.val >= list2.val){
            ListNode next2 = list2.next;
            list2.next = list1;
            list1 = list2;
            list1.next = mergeTwoLists2(list1.next,next2);
        }else {
            list1.next = mergeTwoLists2(list1.next,list2);
        }
        return list1;
    }

    //递归实现合并两个链表，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
    //如果l1<l2:l1.next->merge(l1.next,l2)
    //如果l2<l1:l2.next->merge(l2.next,l2)
    /*
            1 -> 2 -> 4 , 1 -> 3 -> 4
  层      条件        栈的顺序：
  0       0          list1           list2            过程
  1       l2.next    1->2->4         1->3->4                                list1此时是1，next指向1->2->3->4->4，返回1->1->2->3->4->4
  2       l1.next    1->2->4         3->4              l2插入，l1变化         list1此时是1，next指向2->3->4->4，返回1->2->3->4->4
  3       l1.next    2->4            3->4             不符合，l1继续指向       list1此时是2，next指向3->4->4，返回2->3->4->4
  4       l2.next    4               3->4             不符合，l1继续指向       list2此时是3，next指向4->4，返回3->4->4
  5       l2.next    4               4                不符合，l1继续指向       list2此时是4，next指向4，返回4->4
  6                  4               null             返回给上一层list1：4
            *
            * */
    public static ListNode mergeTwoLists3(ListNode list1, ListNode list2) {
        if (list2 == null){
            return list1;
        }else if (list1 == null){
            return list2;
        }else if (list1.val >= list2.val){
            list2.next = mergeTwoLists3(list1,list2.next);
            return list2;
        }else {
            list1.next = mergeTwoLists3(list1.next,list2);
            return list1;
        }
    }
}
